#include "StdAfx.h"
#include "QuadTreeNode.h"
#include "FEngineException.h"
#include "CoreEngine.h"

using namespace std;

namespace FEngine
{
	
	QuadTreeNode::QuadTreeNode(float _size)
		: mSize(_size)
	{
		mParentNode		= NULL;
		mAABB			= new AABB(Vector3(_size, 0, _size), Vector3(_size, 1.0f, _size));
		mInversedDeep	= 0;
		mVisibility		= VISIBILITY_NONE;
		
		mChildNode[0]	= NULL;
		mChildNode[1]	= NULL;
		mChildNode[2]	= NULL;
		mChildNode[3]	= NULL;
	}

	QuadTreeNode::QuadTreeNode(const Vector3& _minPoint, float _size, int _inversedDeep, QuadTreeNode* _parentNode)
		: mSize(_size), mInversedDeep(_inversedDeep)
	{
		mParentNode		= _parentNode;
		mAABB			= new AABB(_minPoint, Vector3(_minPoint.x + _size, 1.0f, _minPoint.z + _size));
		mVisibility		= VISIBILITY_NONE;
		
		mChildNode[0]	= NULL;
		mChildNode[1]	= NULL;
		mChildNode[2]	= NULL;
		mChildNode[3]	= NULL;
	}
	
	QuadTreeNode* QuadTreeNode::_initialize(float _size)
	{
		mSize			= _size;
		mParentNode		= NULL;
		mAABB			= new AABB(Vector3(_size, 0, _size), Vector3(_size, 1.0f, _size));
		mInversedDeep	= 0;
		mVisibility		= VISIBILITY_NONE;
		
		mChildNode[0]	= NULL;
		mChildNode[1]	= NULL;
		mChildNode[2]	= NULL;
		mChildNode[3]	= NULL;

		return this;
	}
	
	QuadTreeNode* QuadTreeNode::_initialize(const Vector3& _minPoint, float _size, int _inversedDeep, QuadTreeNode* _parentNode)
	{
		mSize			= _size;
		mInversedDeep	= _inversedDeep;
		mParentNode		= _parentNode;
		mAABB			= new AABB(_minPoint, Vector3(_minPoint.x + _size, 1.0f, _minPoint.z + _size));
		mVisibility		= VISIBILITY_NONE;
		
		mChildNode[0]	= NULL;
		mChildNode[1]	= NULL;
		mChildNode[2]	= NULL;
		mChildNode[3]	= NULL;

		return this;
	}

	QuadTreeNode::~QuadTreeNode()
	{
		for (int i = 0; i < 4; ++i)
		{
			if (mChildNode[i])
				delete mChildNode[i];
		}
	}
	
	Vector3 QuadTreeNode::getCenterPosition() const
	{
		return mAABB->center();
	}
	
	AABB* QuadTreeNode::getAABB() const
	{
		return mAABB;
	}
	
	float QuadTreeNode::getSize() const
	{
		return mSize;
	}
	
	int QuadTreeNode::getInversedDeep() const
	{
		return mInversedDeep;
	}
	
	NodeVisibility QuadTreeNode::isVisible() const
	{
		return mVisibility;
	}
	
	QuadTreeNode* QuadTreeNode::getParentNode() const
	{
		return mParentNode;
	}
	
	list<QuadTreeNode*> QuadTreeNode::getChildren() const
	{
		list<QuadTreeNode*> list;
		
		for (int i = 0; i < 4; ++i)
		{
			if (mChildNode[i])
				list.push_back(mChildNode[i]);
		}

		return list;
	}
	
	QuadTreeNode* QuadTreeNode::addObject(const Vector2& _pos, QuadTreeNode* _nodeToCreate)
	{
		// Check if the position is insinde the limits of this node
		QuadTreeManager::SquarePosition squarePos = isPositionInLimit(_pos);

		// The node is outside the limits

		if (squarePos == QuadTreeManager::SQUARE_OUTSIDE)
			return NULL;
		
		// This node is the smallest node we can find, so return it
		if (mInversedDeep == 0)
			return this;
		
		// If we can find a smaller node to contains the object, create or find it
		if (mChildNode[squarePos] == NULL)
		{
			if (mInversedDeep - 1 == 0)
				mChildNode[squarePos] = _nodeToCreate->_initialize(_getChildPosition(squarePos), mSize / 2.0f, mInversedDeep - 1, this);
			else
				mChildNode[squarePos] = new QuadTreeNode(_getChildPosition(squarePos), mSize / 2.0f, mInversedDeep - 1, this);
		}

		return mChildNode[squarePos]->addObject(_pos, _nodeToCreate);
	}
	
	QuadTreeManager::SquarePosition QuadTreeNode::isPositionInLimit(const Vector2& _pos)
	{
		float minX		= mAABB->getMinPoint().x;
		float centerX	= mAABB->center().x;
		float maxX		= mAABB->getMaxPoint().x;
		float minY		= mAABB->getMinPoint().z;
		float centerY	= mAABB->center().z;
		float maxY		= mAABB->getMaxPoint().z;
		
		if (_pos.x >= minX && _pos.x < centerX &&
			_pos.y >= minY && _pos.y < centerY)
			return QuadTreeManager::SQUARE_LEFT_BOTTOM;
		
		if (_pos.x >= minX && _pos.x < centerX &&
			_pos.y >= centerY && _pos.y < maxY)
			return QuadTreeManager::SQUARE_LEFT_TOP;
		
		if (_pos.x >= centerX && _pos.x < maxX &&
			_pos.y >= minY && _pos.y < centerY)
			return QuadTreeManager::SQUARE_RIGHT_BOTTOM;
		
		if (_pos.x >= centerX && _pos.x < maxX &&
			_pos.y >= centerY && _pos.y < maxY)
			return QuadTreeManager::SQUARE_RIGHT_TOP;

		return QuadTreeManager::SQUARE_OUTSIDE;
	}
	
	void QuadTreeNode::_addChildNode(QuadTreeNode* _childNode)
	{
		Vector3 childCenterPos = _childNode->getCenterPosition();
		QuadTreeManager::SquarePosition squarePos = isPositionInLimit(Vector2(childCenterPos.x, childCenterPos.z));

		if (squarePos == QuadTreeManager::SQUARE_OUTSIDE)
			throw FEngineException("QuadTreeNode", "_addChildNode", "Cannot add a child node which is not inside the node's limits.");

		if (mChildNode[squarePos] != NULL)
			throw FEngineException("QuadTreeNode", "_addChildNode", "Cannot add a child node when there is already a child node");

		mChildNode[squarePos] = _childNode;
		_childNode->_setParentNode(this);
	}
	
	void QuadTreeNode::_setParentNode(QuadTreeNode* _parentNode)
	{
		if (mParentNode != NULL)
			throw FEngineException("QuadTreeNode", "_addParentNode", "Cannot add a parent node to a node which already have a parent node");

		mParentNode = _parentNode;
	}
	
	Vector3 QuadTreeNode::_getChildPosition(QuadTreeManager::SquarePosition _pos)
	{
		Vector3 childPos;

		switch (_pos)
		{
			case QuadTreeManager::SQUARE_OUTSIDE:
				throw FEngineException("QuadTreeNode", "_getChildPosition", "Cannot find the position of an object outside the node's limits");
			
			case QuadTreeManager::SQUARE_LEFT_BOTTOM:
				childPos = mAABB->getMinPoint();
				break;

			case QuadTreeManager::SQUARE_LEFT_TOP:
				childPos = mAABB->getMinPoint() + Vector3(0, 0, mSize / 2.0f);
				break;
			
			case QuadTreeManager::SQUARE_RIGHT_BOTTOM:
				childPos = mAABB->getMinPoint() + Vector3(mSize / 2.0f, 0, 0);
				break;

			case QuadTreeManager::SQUARE_RIGHT_TOP:
				childPos = mAABB->getMinPoint() + Vector3(mSize / 2.0f, 0, mSize / 2.0f);
				break;
		}

		return childPos;
	}
	
	int QuadTreeNode::_computeFrustumCulling(std::list<QuadTreeNode*>* _listVisibleNodes, float _maxView)
	{
		// Reset the visibility
		_forceVisibility(VISIBILITY_NONE, NULL);
		
		mVisibility = CoreEngine::getInstance()->getCamera()->isVisible(mAABB, true);

		if (mVisibility == VISIBILITY_NONE)
			return 0;

		if (mInversedDeep == 0)
		{
			_listVisibleNodes->push_back(this);
			return 1;
		}

		if (mVisibility == VISIBILITY_TOTAL)
		{
			return _forceVisibility(VISIBILITY_TOTAL, _listVisibleNodes);
		}

		// Partially visible
		int numberVisibility = 0;
		for (int i = 0; i < 4; ++i)
		{
			if (mChildNode[i])
				numberVisibility += mChildNode[i]->_computeFrustumCulling(_listVisibleNodes, _maxView);
		}
		return numberVisibility;
	}
	
	int QuadTreeNode::_forceVisibility(NodeVisibility _visibility, std::list<QuadTreeNode*>* _listVisibleNodes)
	{
		if (_visibility == VISIBILITY_TOTAL)
		{
			mVisibility = _visibility;

			if (mInversedDeep == 0)
			{
				_listVisibleNodes->push_back(this);
				return 1;
			}
			
			int numberVisible = 0;
			for (int i = 0; i < 4; ++i)
			{
				if (mChildNode[i])
					numberVisible += mChildNode[i]->_forceVisibility(_visibility, _listVisibleNodes);
			}
			return numberVisible;
		}

		mVisibility = _visibility;
		for (int i = 0; i < 4; ++i)
		{
			if (mChildNode[i])
				mChildNode[i]->_forceVisibility(_visibility, NULL);
		}
		return 0;
	}
	
	void QuadTreeNode::_addToListIfFinal(std::list<QuadTreeNode*>* _listNodes)
	{
		if (mInversedDeep == 0)
			_listNodes->push_back(this);

		else
		{
			for (int i = 0; i < 4; ++i)
			{
				if (mChildNode[i])
					mChildNode[i]->_addToListIfFinal(_listNodes);
			}
		}
	}

} // namespace FEngine
